This invention relates to data storage apparatus. In data processing, it is often necessary to store a set of data values and then, at some later point of time, to test whether a given value is a member of the stored set of values. The simplest method of doing this is to store the data values in a random-access memory. However, this has the disadvantage that the whole memory must be searched to find out whether a given data value is stored in it. This can obviously be very time-consuming. Alternatively, the data values could be stored in a contents-addressable memory, allowing all the stored data values to be compared very rapidly with the given data value. However, contents-addressable memories are very expensive compared with normal random-access memories.
Another method of storing data values is the hash-coding technique described, for example, in an article by Burton H. Bloom in Communications of the ACM, Vol. 13, No. 7, July 1970 pages 422-426. In particular, in "Method 2" described on page 423 of this article, each data value is hash-coded in a plurality of different ways to produce a plurality of different bit addresses. These addresses are used in turn to address a hash area, containing a number of individually addressable bits, and each bit so addressed is set to "1". To test whether a given data value has been stored, this value is hash-coded in the same way, and the hash area is addressed as before.
If all the addressed bits are equal to "1", then it is assumed that the given data value is stored. Our British patent specification No. 1491706 describes another such hash-coding storage arrangement in which, instead of a single hash area, a plurality of separate areas are used.
Such hash-coding storage arrangements can give a faster response time than a simple random-access memory, without being as expensive as a contents-addressable memory. However, one property of a storage arrangement of this type is that it may produce a number of spurious outputs; that is to say, the output may occasionally indicate that a given data value has been stored when, in fact, it has not. As explained in the above-referenced article, in some applications such spruious outputs may not be objectionable, provided they are not too frequent, and any inconvenience caused by them is outweighed by the saving in cost and/or response time.
Nevertheless, it may still be desirable to reduce the number of spurious outputs, and one object of the present invention is to provide a way of doing this.